package leetcode101.dynamic_planning;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code29
 * @Description 494. 目标和
 * 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。
 * 对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
 *
 * 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
 *
 *  
 *
 * 示例：
 *
 * 输入：nums: [1, 1, 1, 1, 1], S: 3
 * 输出：5
 * 解释：
 *
 * -1+1+1+1+1 = 3
 * +1-1+1+1+1 = 3
 * +1+1-1+1+1 = 3
 * +1+1+1-1+1 = 3
 * +1+1+1+1-1 = 3
 *
 * 一共有5种方法让最终目标和为3。
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-22 9:50
 */
public class Code29 {
    public static void main(String[] args) {
        int[] nums = new int[] {1, 1, 1, 1, 1};
        System.out.println(findTargetSumWays(nums, 3));
    }

    public static int ans;

    public static int findTargetSumWays(int[] nums, int target) {
        ans = 0;
        dfs(nums, target, 0, 0);
        return ans;
    }

    public static void dfs(int[] nums, int target, int level, int temp) {
        if (level == nums.length) {
            if (temp == target) {
                ans++;
            }
            return;
        }
        dfs(nums, target, level + 1, temp + nums[level]);
        dfs(nums, target, level + 1, temp - nums[level]);
    }
}
/*
?
说好的动态规划怎么让你dfs出来了?
 */